/**
 * 416. 分割等和子集
 * https://leetcode-cn.com/problems/partition-equal-subset-sum/
 */

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function canPartition(nums) {
  let sum = 0;
  for (let i = 0; i < nums.length; i += 1) {
    sum += nums[i];
  }
  if (sum % 2 !== 0) {
    return false;
  }
  const target = sum / 2;
  const dp = new Array(nums.length + 1);
  for (let i = 0; i <= nums.length; i += 1) {
    dp[i] = new Array(target + 1).fill(false);
  }
  for (let i = 0; i <= nums.length; i += 1) {
    dp[i][0] = true;
  }
  for (let i = 1; i <= nums.length; i += 1) {
    for (let j = 1; j <= target; j += 1) {
      const num = nums[i - 1];
      if (num <= j) {
        dp[i][j] = dp[i - 1][j - num] || dp[i - 1][j];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[nums.length][target];
}

console.log(canPartition([1, 5, 11, 5]) === true);
console.log(canPartition([1, 2, 3, 5]) === false);
console.log(canPartition([1, 5, 10, 6]) === true);
